package 题目集.贡献法;

import org.junit.Test;

/**
 * https://leetcode.cn/contest/weekly-contest-420/problems/count-substrings-with-k-frequency-characters-i/
 */
public class demo05_字符至少出现K次的子字符串 {
    /**
     * 思路：滑动窗口+贡献法
     * 不考虑重复区间的情况下，每次出现字母数为k的区间 l,r
     * l,r对答案的贡献为（l+1）*(len-r)
     * 重复区间的贡献度  例如  z a c b a b d,k=2
     * 上一个区间的贡献度 和 当前 区间有一个交集  即上一个区间左边界之前的数提供的贡献度都是重合的
     * 所以可以把这部分剪掉，即有重合区间的贡献度：(l-pre_l)*(len-r)
     *
     * @param s
     * @param k
     * @return
     */
    public int numberOfSubstrings(String s, int k) {
        char[] chars = s.toCharArray();
        /*滑动窗口中每个字母的次数*/
        int[] cnt = new int[26];
        /*滑动窗口中最大的次数*/
        int pre = 0;
        int res = 0;
        for (int l = 0, r = 0; r < chars.length; r++) {
            cnt[chars[r] - 'a']++;
            if (cnt[chars[r] - 'a'] >= k) {
                while (cnt[chars[r] - 'a'] >= k) {
                    cnt[chars[l++] - 'a']--;
                }
                res += (l - pre) * (chars.length - r);
                pre = l ;
            }
        }
        return res;
    }

    @Test
    public void test() {
        /**
         * h hx
         */
        System.out.println(numberOfSubstrings("abacb", 2));
    }
}
